[POJ 3683]Priest John's Busiest Day

原题链接:POJ 3683
题目大意:有$n$对人结婚仪式,对第$i$场结婚仪式开始或结束时需要进行一个时长为$D_i$的特殊仪式,起始时间是$S$,结束时间是$T$则要么选$[S,S + D_i]$,要么选$[T - D_i,T]$这两个时间段之一.问每场婚礼是否都至少有一个特殊仪式.如果有,则额外输出具体方案.
注意:牧师Jhon虽然不能同时出现在两个婚礼,但是他在两个婚礼之间赶路的时间可以忽略.

数据范围:
$1 \leq n \leq 1000$
题目的时间以$hh:mm$的格式给出

样例输入:

2
08:00 09:00 30
08:15 09:00 20

样例输出

YES
08:00 08:30
08:40 09:00

这题乍看上去,可能是一个关于时间的贪心.但是这题每个人的选择都是有两种的,所以不大好做,形式上比较接近$2-SAT$问题.把$A_{i,0}$看成是第$i$场婚礼去了开头,$A_{i,1}$看成是去了结尾.考虑如何建图:先以$O(N^2)$的方式遍历每场婚礼,两场婚礼分别为$i$和$j$,若$A_{i,p}$和$A_{j,q}$($p,q\in \{0,1\}$)时间段上有冲突,就说明两场婚礼肯定不能同时去做特殊仪式,在图上对$i + p *N$和$j + (1 - q)*N$连边,$j + q * N$和$j + q * N$和$i + (1 - p)*N)连边.

具体来说,我们先划分成四种情况,与两边是否是第一段开头有关:
①00
即两个开头的时间冲突了,判据是起始时间是否覆盖比开头高就行了

if(min(S{i] + D[i],S[j] + D{j]) > max(S{i],S[j]))
    add(i,j + n), add(j,i + n)

②01
即前者的开头和后者的结尾段冲突了,判断两者是否相交上了

if(min(S[i] + D[i],T[j]) > max(S[i],T[j] - D[j]))
    add(i,j),add(j + n,i + n);

当然你也可以写成一个区间判断覆盖的形式,不过我这里直接用白书的写法来解决这个问题了,比那个区间覆盖的方式稍微好写一点,如下:

bool collision(int a, int b, int c, int d) {
	if (a >= c && a < d || b > c && b <= d || a <= c && b >= d) return 1;
	return 0;
}

另外两种就不特别说明了
之后判断是否有解,如果有解的话,在$SCC$之后的新图里,如果拓扑排序的位置中,$a$的位置早于$\lnot a$,则把$a$设置成假,另外一个设置成真.最后输出即可

代码:

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005,M = 4e6+7;
int edge[M],succ[M],ver[N],idx;
int time_stamp,dfn[N],low[N];
int n,m;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,siz[N];
int din[N],dout[N];
int S[N],T[N],D[N],opid[N],res[N];
void add(int u,int v)
{
	edge[idx] = v;
	succ[idx] = ver[u];
	ver[u] = idx++;
}
void tarjan(int u)
{
	dfn[u] = low[u] = ++time_stamp;
	stk[++top] = u,in_stk[u] = 1;
	for(int i = ver[u];~i;i = succ[i])
	{
		int j = edge[i];
		if(!dfn[j])
		{
			tarjan(j);
			low[u] = min(low[u],low[j]);
		}
		else if(in_stk[j])	
			low[u] = min(low[u],dfn[j]);
	}
	if(dfn[u] == low[u])
	{
		int y;
		++scc_cnt;
		do
		{
			y = stk[top--];
			in_stk[y] = 0;
			id[y] = scc_cnt;
			siz[scc_cnt]++;
		}while(y != u);
	}
}

int main()
{
	memset(ver,-1,sizeof ver);
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)
	{
		int h1,m1,h2,m2;int d;
		scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&d);
		S[i] = h1 * 60 + m1;
		T[i] = h2 * 60 + m2;
		D[i] = d;
	}
	for(int i = 1;i <= n;++i)
		for(int j = 1;j < i;++j)
		{
			//00
			if(min(S[i] + D[i],S[j] + D[j]) > max(S[i],S[j]))
			{
				add(i,j + n);
				add(j,i + n);
			}
			//01
			if(min(S[i] + D[i],T[j]) > max(S[i],T[j] - D[j]))
			{
				add(i,j);
				add(j + n,i + n);
			}
			//10
			if(min(T[i],S[j] + D[j]) > max(T[i] - D[i],S[j]))
			{
				add(i + n,j + n);
				add(j,i);
			}
			//11
			if(min(T[i],T[j]) > max(T[i] - D[i],T[j] - D[j]))
			{
				add(i + n,j);
				add(j + n,i);
			}
		}
	for(int i = 1;i <= 2 * n;++i)
		if(!dfn[i])
			tarjan(i);
	reverse(stk + 1,stk + 1 + 2 * n);
	int ok = 1;
	for(int i = 1;i <= n;++i)
	{
		if(id[i] == id[i + n])
		{
			ok = 0;
			break;
		}
	}
		
	if(!ok)	puts("NO");
	else
	{
		puts("YES");
		for(int i = 1;i <= n;++i)
		{
			if(id[i] > id[i + n])
				printf("%02d:%02d %02d:%02d\n",(T[i] - D[i]) / 60,(T[i] - D[i]) % 60,T[i] / 60,T[i] % 60);
			else 
				printf("%02d:%02d %02d:%02d\n",S[i] / 60,S[i] % 60,(S[i] + D[i]) / 60,(S[i] + D[i]) % 60);
		}

	}
    return 0;
}